package leetcode每日一题.leetcode20212;

import java.util.*;

/**
 * 实现 MaxHeap 和 MinHeap
 * 分析数据结构：
 *      主要是分析类的构建和具体需要实现哪些API
 *      堆本质上可以看成是一个完全二叉树，本质上是一个树结构，但是我们可以通过数组这个简单的数据结构来实现
 *      给定一个数组，我们如何构建堆就是关键的问题
 */
@SuppressWarnings("all")
public class Q010_1_手动实现大小顶堆 {

    /**
     * 实现大顶堆
     */
    class MaxHeap {

    }


    /**
     * 实现小顶堆
     */
    class MinHeap {
        int[] heap; // 堆容器
        int maxSize; // 堆的最大容量
        int curSize; // 堆的当前容量

        public MinHeap(int maxSize) {
            heap = new int[maxSize];
            this.maxSize = maxSize;
        }

        public int size() { // 返回当前堆的容量
            return curSize;
        }

        public int peek() { // 查看当前堆顶元素(堆中最小元素)
            if (curSize == 0) {
                throw new NullPointerException("heap is empty");
            }
            return heap[0];
        }

        /**
         * 对于删除操作而言相对比较复杂，在数组中如果直接删除第一个元素，则整个数组的后面的元素都需要
         * 向前移动，这个代价太大了，但是对于删除数组的最后一个元素，则代价非常小，甚至可以控制在O(1)
         * 的时间复杂度内。所以我们删除操作的整体思路：先将堆顶元素与数组的末尾元素进行一次交换，然后
         * 让当前数组的长度-1，由于此时可能会破坏当前堆的性质，所以我们调用自顶向下的方法进行调整，整
         * 体的时间复杂度就可以控制在O(logn)的范围内
         * @return
         */
        public int poll() { // 删除堆顶元素，并返回删除之前的堆顶元素
            if (curSize == 0) {
                throw new NullPointerException("heap is empty");
            }
            int heapTop = heap[0];
            swap(heap[0],heap[curSize]);
            curSize--;
            heapifyDown(0);
            return heapTop;
        }

        public void push(int val) { // 向堆中添加元素
            if (curSize >= maxSize) {
                throw new RuntimeException("heap full, can't push any one element");
            }
            heap[curSize] = val;
            heapifyUp(curSize);
            curSize++;
        }

        public void heapifyUp(int curIndex) { // 向上堆化，辅助push操作
            if (curIndex == 0) { // 表明当前已经是root节点的位置了，直接返回
                return;
            }
            int parent = (curIndex - 1) / 2; // 获取当前位置索引的父位置索引
            if (heap[curIndex] >= heap[parent]) { // 如果添加之后满足小顶堆的性质，直接返回
                return;
            }
            swap(heap[curIndex],heap[parent]); // 交换
            heapifyUp(parent); // 递归进行下一次交换
        }

        public void heapifyDown(int curIndex) { // 向下堆化，辅助poll操作
            int smallest = curIndex; // 占位作用
            for (int x :new int[] {2 * curIndex + 1, 2 * curIndex + 2}) {
                if (x < curSize && heap[x] > heap[smallest]) {
                    smallest = x;
                }
            }
            if (smallest == curIndex) {
                return;
            }
            swap(heap[curIndex],heap[smallest]);
            heapifyDown(smallest);
        }

        public void swap(int x, int y) { // 交换函数，辅助堆化过程
            int temp = x;
            x = y;
            y = temp;
        }

        public boolean hasLeftChild(int index) { // 判断当前节点是否有左子节点,辅助heapifyDown
            return 2 * index + 1 < maxSize;
        }

        public boolean hasRightChild(int index) { // 判断当前节点是否有右子节点,辅助heapifyDown
            return 2 * index + 2 < maxSize;
        }
    }

    static class Pair {
        int val;
        int count;
        public Pair(int val,int count) {
            this.val = val;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        HashMap<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Pair> heap = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o2.count-o1.count;
            }
        });
        Pair pair1 = new Pair(1,2);
        Pair pair2 = new Pair(-1,2);
        Pair pair3 = new Pair(2,3);
        Pair pair4 = new Pair(3,3);
        heap.add(pair1);
        heap.add(pair2);
        heap.add(pair3);
        heap.add(pair4);

        for (Pair pair : heap) {
            System.out.println(pair.val + ":" + pair.count);
        }
    }
}
